package Tree;

/**
 * 分配一些值到一棵树上，保证数的奇数层值的和 最接近 偶数层值的和
 * <p>
 * examples:
 * 1
 * 2 3
 * 4
 *
 * @author Liaorun
 */
public class EvenEqOldLevelValue {

    public static void main(String[] args) {

    }

    /**
     * @param n 树一共有n个节点
     * @param k 奇数层的节点个数
     * @return
     */
    public static int[] team(int n, int k) {
        // 等差数列求和，算出所有节点的和
        int sum = (n + 1) * n / 2;
        // 1. sum 为偶数 example: sum=10 => p1 = 5
        // 2. sum 为奇数 example: sum=11 => p1 = 5；p2 = 6
        int p1 = sum / 2;
        int p2 = (sum + 1) / 2;
        int[] ans = generate(p1, n, k);

        // 第一次没有找到结果 && sum 是奇数(最低位为1)
        if (ans == null && (sum & 1) == 1) {
            // 在找一遍
            ans = generate(p2, n, k);
        }

        return ans != null ? ans : new int[]{-1};
    }

    /**
     * @param x 最终需要的累加和
     * @param n 一共有多少个数字
     * @param k 一定要从中选k个，累加和正好为x
     * @return
     */
    public static int[] generate(int x, int n, int k) {
        // 1 + 2 + 3 + ... + k
        int sumMinK = (k + 1) * k / 2;
        // 一个数字能提升的最大幅度
        int range = n - k;
        if (x < sumMinK || x > sumMinK + k * range) {
            return null;
        }

        // 整体需要提升的总幅度
        int add = x - sumMinK;
        // 需要整体搬家过去的数的个数
        int rightSize = add / range;
        // 中间的一个数，单独跳多少呢？
        int midIndex = (k - rightSize) + (add % range);
        // 左变还剩下几个数
        int leftSize = k - rightSize - (add % range == 0 ? 0 : 1);
        int[] ans = new int[k];

        for (int i = 0; i < leftSize; i++) {
            ans[i] = i + 1;
        }

        // 是否存在单独搬运的那个数
        if (add % range != 0) {
            // 有的话，记录这个数需要跳几步到对应的位置
            ans[leftSize] = midIndex;
        }

        // 记录跳到最右侧的那些数字
        for (int i = k - 1, j = 0; j < rightSize; i--) {

            ans[i] = n - j;
            j++;
        }

        return ans;
    }
}
